#pragma once

#include <iostream>
#include <string>
#include <vector>
#include "../Queue/Queue.h"


enum class TraversalType:uint8_t
{
	// 广度优先
	BreadthFirst,
	// 深度优先
	DepthFirst
};

enum class DepthTravesalType:uint8_t
{
	// 前序
	Prev,
	// 中序
	Inorder,
	// 后序
	Post
};


template<typename T, typename NodeType>
struct NodeBase
{
	NodeBase():data(),parent(nullptr),left(nullptr),right(nullptr){}
	NodeBase(const T& inData):data(inData),parent(nullptr),left(nullptr),right(nullptr){}
		
	T data;
	NodeType* parent;
	NodeType* left;
	NodeType* right;
};

template<typename T>
struct BTNode: public NodeBase<T, BTNode<T>>
{
	using NodeBase<T, BTNode<T>>::NodeBase;
};


template<typename T, typename NodeType=BTNode<T>>
class BinaryTreeBase
{
public:
	using Node = NodeType;
public:

	BinaryTreeBase();
	virtual ~BinaryTreeBase();

	void ShowData(const TraversalType& traversalType, const DepthTravesalType& depthType=DepthTravesalType::Prev) const;
	void ShowTreeGraph() const;
	int Size() const;

	/**
	 * 获取树的高度
	 * @return 
	 */
	int Height() const;
	
	/**
	 * 插入元素
	 * @param element 
	 */
	void Insert(const T& element);

	/**
	 * 删除节点
	 * @param deletedNode 
	 */
	void Delete(Node* deletedNode);

	/**
	 * 查找最小值
	 * @return 
	 */
	Node* FindMin(Node* rootNode) const;

	/**
	 * 获取根节点
	 * @return 
	 */
	Node* Root() const;

protected:
	/**
	 * 递归计算树高度
	 * @return 
	 */
	int GetHeightRecursively(const Node* childRoot) const;

	/**
	 * 填充二叉树节点绘制缓冲区
	 * @param childRoot 
	 * @param buffer 
	 * @param row 缓冲区行
	 * @param col 缓冲区列
	 * @param hier 数的总层数
	 */
	void FillDrawBuffer(Node* childRoot, std::vector<std::vector<std::string>>& buffer,
						int row, int col, int hier) const;
private:
	/**
	 * 递归插入节点
	 * @param element 
	 * @param childRoot 
	 */
	void InsertRecursively(const T& element, Node*& childRoot);
	
	/**
	 * 广度优先 - 显示数据
	 */
	void ShowDataBreadthFirst() const;

	/**
	 * 深度优先 - 显示数据
	 */
	void ShowDataDepthFirst(const DepthTravesalType& depthType) const;
	
	/**
	 * 深度优先 -> 前序遍历
	 * @param childRoot 
	 */
	void DepthTraversal_Prev(Node* childRoot) const;

	/**
	 * 深度优先 -> 中序遍历
	 * @param childRoot 
	 */
	void DepthTraversal_Inorder(Node* childRoot) const;

	/**
	 * 深度优先 -> 后序遍历
	 * @param childRoot 
	 */
	void DepthTraversal_Post(Node* childRoot) const;
	
	/**
	 * 递归删除
	 * @param childRoot 
	 * @param deletedNode 
	 * @return 
	 */
	Node* DeleteRecursively(Node* childRoot, Node* deletedNode);
protected:
	int size;
	Node* root;
};


template <typename T, typename NodeType>
BinaryTreeBase<T, NodeType>::BinaryTreeBase():
size(0),
root(nullptr)
{
}

template <typename T, typename NodeType>
BinaryTreeBase<T, NodeType>::~BinaryTreeBase()
{
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::ShowData(const TraversalType& traversalType, const DepthTravesalType& depthType) const
{
	std::cout << "Show BST: \n";
	std::cout << "Size: " << size << "\n";

	switch(traversalType)
	{
	case TraversalType::BreadthFirst:
		ShowDataBreadthFirst();
		break;

	case TraversalType::DepthFirst:
		ShowDataDepthFirst(depthType);
		break;
	}
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::ShowTreeGraph() const
{
	if(!root)
		return;

	// 矩阵行数 == 树层级数
	int matrixHeight = Height() + 1;
	// 矩阵列数 == (2 * 树最深层的最大节点数) - 1
	int matrixWidth = std::pow(2, matrixHeight) - 1;
	std::vector<std::vector<std::string>> treeMatrix(matrixHeight, std::vector<std::string>(matrixWidth, " "));

	FillDrawBuffer(root, treeMatrix, 0, (matrixWidth - 1)/2, matrixHeight);

	for(const auto& row : treeMatrix)
	{
		for(const auto& item : row)
		{
			std::cout << item ;
		}
		std::cout << std::endl;
	}
	std::cout << "\n" << std::endl;
}

template <typename T, typename NodeType>
int BinaryTreeBase<T, NodeType>::Size() const
{
	return size;
}

template <typename T, typename NodeType>
int BinaryTreeBase<T, NodeType>::Height() const
{
	if(root)
	{
		// 如果 root 不为空
		int lHeight = GetHeightRecursively(root->left);
		int rHeight = GetHeightRecursively(root->right);

		// 返回两者中大的那个
		// + 根节点高度
		return (lHeight < rHeight ? rHeight : lHeight) + 1;
	}
	else
	{
		// 如果 root 为空，说明树为空，高度不存在
		return -1;
	}
}

template <typename T, typename NodeType>
int BinaryTreeBase<T, NodeType>::GetHeightRecursively(const Node* childRoot) const
{
	if(childRoot)
	{
		// 如果 childRoot 不为空
		int lHeight = GetHeightRecursively(childRoot->left);
		int rHeight = GetHeightRecursively(childRoot->right);

		// 返回两者中大的那个
		// + 根节点高度
		return (lHeight < rHeight ? rHeight : lHeight) + 1;
	}
	else
	{
		// 如果 childRoot 为空，说明树为空，高度不存在
		return -1;
	}
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::Insert(const T& element)
{
	InsertRecursively(element, root);
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::InsertRecursively(const T& element, Node*& childRoot)
{
	if (childRoot)
	{
		// 如果当前子树根节点不为空
		
		if (element < childRoot->data)
		{
			// 如果插入元素小于当前根节点元素，插入左子树
			// 若在插入前，左子树为空。执行插入后，左子树不为空
			// 说明新节点为当前节点的子节点
			bool bIsNullBefore = childRoot->left == nullptr;
			
			InsertRecursively(element, childRoot->left);
			
			if(bIsNullBefore && childRoot->left)
			{
				childRoot->left->parent = childRoot;
			}
		}
		else if (element > childRoot->data)
		{
			// 如果插入元素大于当前根节点元素，插入右子树
			// 若在插入前，右子树为空。执行插入后，右子树不为空
			// 说明新节点为当前节点的子节点
			bool bIsNullBefore = childRoot->right == nullptr;
			
			InsertRecursively(element, childRoot->right);

			if(bIsNullBefore && childRoot->right)
			{
				childRoot->right->parent = childRoot;
			}
		}
		else
		{
			// 如果当前元素已存在，直接返回
			return;
		}
	}
	else
	{
		// 如果当前子树根节点为空，插入到当前根节点
		childRoot = new Node(element);
		++size;
	}
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::Delete(Node* deletedNode)
{
	if(!(root && deletedNode))
		return;

	if(deletedNode->data < root->data)
	{
		root->left = DeleteRecursively(root->left, deletedNode);
	}
	else if(deletedNode->data > root->data)
	{
		root->right = DeleteRecursively(root->right, deletedNode);
	}
	else
	{
		// 有0个子节点
		if((root->left == nullptr) && (root->right == nullptr))
		{
			delete root;
			root = nullptr;
		}
		// 有左子节点
		else if(root->right == nullptr)
		{
			Node* temp = root;
			root = root->left;
			delete temp;
		}
		// 有右子节点
		else if(root->left == nullptr)
		{
			Node* temp = root;
			root = root->right;
			delete temp;
		}
		// 有左右子节点
		else
		{
			Node* temp = FindMin(root->right);
			root->data = temp->data;
			root->right = DeleteRecursively(root->right, temp);
		}
		
	}
	--size;
}

template <typename T, typename NodeType>
typename BinaryTreeBase<T, NodeType>::Node* BinaryTreeBase<T, NodeType>::DeleteRecursively(Node* childRoot, Node* deletedNode)
{
	if(!childRoot)
		return nullptr;
	
	if(deletedNode->data < childRoot->data)
	{
		childRoot->left = DeleteRecursively(childRoot->left, deletedNode);
	}
	else if(deletedNode->data > childRoot->data)
	{
		childRoot->right = DeleteRecursively(childRoot->right, deletedNode);
	}
	else
	{
		// 有0个子节点
		if((childRoot->left == nullptr) && (childRoot->right == nullptr))
		{
			delete childRoot;
			childRoot = nullptr;
		}
		// 有左子节点
		else if(childRoot->right == nullptr)
		{
			Node* temp = childRoot;
			childRoot = childRoot->left;
			childRoot->parent = temp->parent;
			delete temp;
		}
		// 有右子节点
		else if(childRoot->left == nullptr)
		{
			Node* temp = childRoot;
			childRoot = childRoot->right;
			childRoot->parent = temp->parent;
			delete temp;
		}
		// 有左右子节点
		else
		{
			Node* temp = FindMin(childRoot->right);
			childRoot->data = temp->data;
			childRoot->right = DeleteRecursively(childRoot->right, temp);
		}
	}

	return childRoot;
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::ShowDataBreadthFirst() const
{
	std::cout << "BreadthFirst \n";
	if(!root)
		return;

	// 获取树高度
	int treeHeight = Height();
	// 树最底层的节点数 = pow(2, 树高度)
	// root 为0层
	int dequeueCapacity = pow(2, treeHeight);
	// 初始化队列
	Queue<Node*> queue(dequeueCapacity);
	queue.Enqueue(root);

	// 当队列不为空时，循环
	while(!queue.IsEmpty())
	{
		Node* temp = queue.Front();
		std::cout << temp->data << " ";
		if(temp->left)
			queue.Enqueue(temp->left);
		if(temp->right)
			queue.Enqueue(temp->right);

		queue.Dequeue();
	}
	std::cout << std::endl;
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::ShowDataDepthFirst(const DepthTravesalType& depthType) const
{
	std::cout << "DepthFirst: ";
	if(!root)
		return;
	
	switch(depthType)
	{
	case DepthTravesalType::Prev:
		std::cout << "Prev \n";
		DepthTraversal_Prev(root);
		break;

	case DepthTravesalType::Inorder:
		std::cout << "Inorder \n";
		DepthTraversal_Inorder(root);
		break;

	case DepthTravesalType::Post:
		std::cout << "Post \n";
		DepthTraversal_Post(root);
		break;
	}
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::DepthTraversal_Prev(Node* childRoot) const
{
	// 前序遍历
	// 顺序：根节点->左子树->右子树
	if(childRoot)
	{
		std::cout << childRoot->data << " ";
		DepthTraversal_Prev(childRoot->left);
		DepthTraversal_Prev(childRoot->right);
	}
	else
	{
		return;
	}
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::DepthTraversal_Inorder(Node* childRoot) const
{
	// 中序遍历
	// 顺序：左子树->根节点->右子树
	if(childRoot)
	{
		DepthTraversal_Inorder(childRoot->left);
		std::cout << childRoot->data << " ";
		DepthTraversal_Inorder(childRoot->right);
	}
	else
	{
		return;
	}
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::DepthTraversal_Post(Node* childRoot) const
{
	// 后序遍历
	// 顺序：左子树->右子树->根节点
	if(childRoot)
	{
		DepthTraversal_Post(childRoot->left);
		DepthTraversal_Post(childRoot->right);
		std::cout << childRoot->data << " ";
	}
	else
	{
		return;
	}
}

template <typename T, typename NodeType>
void BinaryTreeBase<T, NodeType>::FillDrawBuffer(Node* childRoot, std::vector<std::vector<std::string>>& buffer, int row,
	int col, int hier) const
{
	if(!childRoot)
		return;

	// 填充元素
	buffer[row][col] = std::to_string(childRoot->data);

	// 计算下一层元素列位置偏移
	// hier - row == 当前层数
	// 当前层数 - 1 == 下一层数
	// 层数 - 1 = 当前层的实际树高
	// hier - row - 2 == 下一层的实际树高
	// gap == 下一层子树的最深层的最大节点数
	int gap = std::pow(2, hier - row - 2);

	if(childRoot->left)
		FillDrawBuffer(childRoot->left, buffer, row + 1, col - gap, hier);
	else if( row + 1 < hier)
		buffer[row+1][col - gap] = ".";
	
	if(childRoot->right)
		FillDrawBuffer(childRoot->right, buffer, row + 1, col + gap, hier);
	else if( row + 1 < hier)
		buffer[row+1][col + gap] = ".";
}

template <typename T, typename NodeType>
typename BinaryTreeBase<T, NodeType>::Node* BinaryTreeBase<T, NodeType>::FindMin(Node* rootNode) const
{
	if(rootNode)
	{
		// 二叉搜索树，最小值一直沿着左子树搜索
		Node* finder = rootNode;
		while(finder->left)
			finder = finder->left;

		return finder;
	}
	else
	{
		return nullptr;
	}
}

template <typename T, typename NodeType>
typename BinaryTreeBase<T, NodeType>::Node* BinaryTreeBase<T, NodeType>::Root() const
{
	return root;
}
